package mo.leetcode_top;

import java.util.PriorityQueue;

public class L295 {

    private PriorityQueue<Integer> small = new PriorityQueue<>((r1, r2) -> r2 - r1);
    private PriorityQueue<Integer> large = new PriorityQueue<>();

    public L295() {

    }

    public void addNum(int num) {
        small.add(num);
        large.add(small.poll());
        if (small.size() < large.size()) {
            small.add(large.poll());
        }
    }

    public double findMedian() {
        if (small.size() > large.size()) {
            return small.peek();
        } else {
            return ((double) (small.peek() + large.peek())) / 2;
        }
    }

    public static void main(String[] args) {
        L295 test = new L295();
        test.addNum(1);
        test.addNum(2);
        System.out.println(test.findMedian());
        test.addNum(3);
        System.out.println(test.findMedian());
    }
}
